Nullifiers and Account Abstraction

$$ \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\c#1{\mathsf{#1}} \gdef\kw#1{\textsf{\textbf{#1}}} \gdef\H{\c{H}} $$

Privacy oriented protocols often need a mechanism to do an action anonymously and only once. For example spending a coin, claiming an airdrop, or voting on a proposal.

Question. Why not use signatures or $\H\p{\c{signature}}$ as nullifiers.

Status Quo: Nullifiers

The standard solution is using nullifiers.

$$ \c{nullifier} = \H\p{\c{context}, \c{private\_key}} $$

Typically the zkSNARK would prove

$$ \delim[{ \begin{array}{c} \c{root}, \c{context}, \\ \c{nullifier}, \c{message} \\ \hline \c{merkle\_proof}, \\ \c{private\_key} \end{array} \middle\vert \begin{array}{l} \c{nullifier} = \H\p{\c{context}, \c{private\_key}} \\ \c{public\_key} = \c{derive\_public\_key}\p{\c{private\_key}} \\ \c{verify\_inclusion}\p{\c{merkle\_proof}, \c{public\_key}} \end{array} }] $$

Account Abstraction

Before account abstraction, actions are authorized using ecdsa signatures. The pair $\p{\c{user\_id}, \c{message}, \c{signature}}$ is verified by checking the signature, for example by recovering the public key and hence the user id.

$$ \c{user\_id} = \H\p{\c{ecdsa\_recover}\p{\H\p{\c{message}}, \c{signature}}} $$

The $\c{ecdsa\_verify}$ function has the nice property that it is pure. It is a well-defined computation depending only on its inputs that always gives the same result. It's easy to zkSNARK these.

$$ \delim[{ \begin{array}{c} \c{user\_id}, \c{message} \\ \hline \c{public\_key},\\ \c{signature} \end{array} \middle\vert \begin{array}{l} \c{user\_id} = \H\p{\c{public\_key}}\\ \c{ecdsa\_verify}\p{\c{public\_key}, \H\p{\c{message}}, \c{signature}} \end{array} }] $$

or alternatively we can push the hashes out of the proof

$$ \delim[{ \begin{array}{c} \c{public\_key}, \\ \c{message\_hash} \\ \hline \c{signature} \end{array} \middle\vert \begin{array}{l} \c{ecdsa\_verify}\p{\c{public\_key}, \c{message\_hash}, \c{signature}} \end{array} }] $$

The main downside of the ecdsa signature is that they require the user to keep a secret.

In account abstraction we get rid of explicit private keys and instead use a smart contract with a programmable predicate to check signatures.

$$ \c{wallet}\p{\c{user\_id}}. \c{verify}\p{\H\p{\c{message}}, \c{signature}} $$

This $\c{verify}$ is no longer pure, it depends on the current state of the chain. We can make this dependence explicit:

$$ \c{evm\_verify}\p{\c{chain\_state}, \c{user\_id}, \H\p{\c{message}}, \c{signature}} $$

This predicate is again pure and we can zkSNARK it, providing a commitment to $\c{chain\_state}$ (i.e. a block hash) as public input. The actual implementation of this zkSNARK is non-trivial and requires all full zkEVM implementation. While zkEVM implementations exist, they are quite resource hungry and do not currently appear feasible on mobile devices. I'll ignore this problem for now and wait for the relentless march of progress to solve it.

$$ \delim[{ \begin{array}{c} \c{block\_hash}, \\ \c{user\_id}, \c{message} \\ \hline \c{chain\_state}, \\ \c{signature} \end{array} \middle\vert \begin{array}{l} \c{block\_hash} = \c{state\_hash}\p{\c{chain\_state}} \\ \c{evm\_verify}\p{\c{chain\_state}, \c{user\_id}, \H\p{\c{message}}, \c{signature}} \end{array} }] $$

The problem

If we try to include the above zkEVM abstract signature proof into the semaphore scheme we get this

$$ \delim[{ \begin{array}{c} \c{block\_hash},\c{root},\\ \c{context}, \c{nullifier}, \\\c{message} \\ \hline \c{merkle\_proof}, \c{user},\\ \c{chain\_state}, \\ \c{signature} \end{array} \middle\vert \begin{array}{l} \c{block\_hash} = \c{state\_hash}\p{\c{chain\_state}} \\ \c{evm\_verify}\p{\c{chain\_state}, \c{user}, \H\p{\c{context}, \c{message}}, \c{signature}} \\[1em] \c{nullifier} = \H\p{\c{context}, ???} \\ \c{public\_key} = \c{derive\_public\_key}\p{\c{private\_key}} \\ \c{verify\_inclusion}\p{\c{merkle\_proof}, \c{public\_key}} \end{array} }] $$

The problem is what to use as entropy in the place of $???$ for the nullifier derivation:

$$ \c{nullifier} = \H\p{\c{context}, ???} \\ $$

We may have a private key that we use to produce signatures for the wallet, but even if that is the case it can change over time and does not provide the long-lived guarantees needed for nullifiers. (And being able to change it is a big part of the motivation for account abstraction).

Obfuscation

Assume we can create a black-box function $f$ for any computable function. Would this solve our problem? We can hide the entropy in the program.

Let's say we can take any pure computable function $f$ and turn it into a black box $\hat{f}$ such that we can store and evaluate $\hat{f}$ onchain without anyone being able to see the implementations details of $\hat f$. We could use this to store the user entropy. Let each user generate some private $\c{entropy}$, and create $\hat f(x) = \H\p{\c{entropy}, x}$. Then we can derive nullifiers as:

$$ \delim[{ \begin{array}{c} \c{context}, \c{nullifier} \\ \hline ⋯ \end{array} \middle\vert \begin{array}{l} ⋯ \\ \c{nullifier} = \hat f\p{\c{context}} \\ ⋯ \end{array} }] $$

This works, but it's no better than storing the $\c{entropy}$ directly onchain, and it suffers from the same problem: for a given nullifier we can just enumerate all user's $\hat f$ and find the one that satisfies $\c{nullifier} = \hat f\p{\c{context}}$. This will identify the user.

We need to modify $\hat f$ to prevent such enumeration. We can fix this by making the evaluation conditional on a user provided signature.

$$ f(\c{chain\_state}, x, \c{signature}) = \begin{cases} \H\p{\c{entropy}, x} & \c{evm\_verify\p{\c{chain\_state},\c{user\_id},x,\c{signature}}}\\ ⊥ & \text{otherwise} \end{cases} $$

Note that $\c{user\_id}$ can be hardcoded as we generate an $\hat f$ for each user. We can theoretically build such an $hat f$ using indistinguishability obfuscation ($\mathcal{iO}$), though current schemes are very inefficient. See SW13 for examples of protocols build using $\mathcal{iO}$. Note that it is and extremely powerful primitive that can be used to construct zkSNARKS and many other cryptographic primitives.

This solves the enumeration problem as long as the attacker is not able to produce valid signature. But the attacker can trivially generate a $\p{\c{chain\_state}, \c{signature}}$ pair if it can substitute any $\c{chain\_state}$. We need a way to make sure $\c{chain\_state}$ is indeed part of the chain. Just proving that $\c{chain\_state}$ is part of the chain alone is also not enough. This allows any historical owner to call the function, even if they are no longer owner. We need a way to make sure $\c{chain\_state}$ is onchain and recent. The onchain part can be dealt with by deterministically checking consensus rules (baring long-range attacks). The recency part requires a new protocol however, as the current time is stateful.

For the zkSNARK this is not a problem as we can expose the $\c{block\_hash}$ as a public input and make the recency check part of the verification logic. There doesn't seem to be a similar mechanism for obfuscated functions.

Recent block oracle

If we had some oracle that givens us a recent $\c{chain\_state}$ we can simplify the $\c{evm\_verify}$ and solve the problem in $\hat f$. But building such an oracle so it can be used in $\hat f$ is hard.

Suppose we have an oracle that on request signs the latest $\c{chain\_state}$ with some $\c{signature}$ such that we can use a pure computable function $\c{verify}\p{\c{chain\_state}, \c{signature}}$. The first problem is that this introduces a new long running private key, which was exactly what we were trying to avoid. Turning this into a smart contract account just recurses the problem. The second problem is that the signature can simply be replayed. While this limits an attacker to old $\c{chain\_state}$, a notable improvement, it's not where I'd like it yet.

Maybe we could make it such that the signature is also tied to the instance. That way the only usable $\c{chain\_state}$ for a nullifier is the one that was first used for that nullifier. This seems reasonable because now a leak of old keys only de-anonymizes the nullifiers made with those keys. Furthermore we can consider this $\c{signature}$ to be a secret between the oracle and the user.

$$ f\p{ \begin{array}{c} \c{chain\_state}, x,\\ \c{oracle\_signature},\\ \c{user\_signature} \end{array} } = \begin{cases} \H\p{\c{entropy}, x} & \begin{array}{l} \c{oracle\_verify}\p{\H\p{\c{chain\_state}, \c{user\_id}, x}, \c{oracle\_signature}} \\ \c{evm\_verify\p{\c{chain\_state},\c{user\_id},x,\c{user\_signature}}} \end{array}\\ ⊥ & \text{otherwise} \end{cases} $$

Again we generate obfuscated $\hat f$ with $\c{user\_id}$ and $\c{entropy}$ hardcoded. The zkp becomes

$$ \delim[{ \begin{array}{c} \c{block\_hash},\c{root},\\ \c{context}, \c{nullifier}, \\\c{message} \\ \hline \c{merkle\_proof}, \c{user},\\ \c{chain\_state}, \\ \c{user\_signature}_1, \\ \c{user\_signature}_2, \\ \c{oracle\_signature} \end{array} \middle\vert \begin{array}{l} \c{block\_hash} = \c{state\_hash}\p{\c{chain\_state}} \\ \c{evm\_verify}\p{\c{chain\_state}, \c{user\_id}, \H\p{\c{context}, \c{message}}, \c{user\_signature}_1} \\[1em] \c{nullifier} = \hat f\p{\c{chain\_state}, \c{context}, \c{oracle\_signature}, \c{user\_signature}_2} \\ \c{public\_key} = \c{derive\_public\_key}\p{\c{private\_key}} \\ \c{verify\_inclusion}\p{\c{merkle\_proof}, \c{public\_key}} \end{array} }] $$

Other solutions

Secret key nullifiers?

Let's say we have some secret $\c{entropy}$ and derive nullifiers as

$$ \c{nullifier} = \H\p{\c{entropy}, \c{user\_id}, \c{context}} $$

This works as long as only the user can make queries. Above we derived an elaborate scheme using $\mathcal{iO}$ to achieve this, but there are alternatives such as a trusted server, MPC, FHE, etc.

Identity based encryption?

Maybe identity based encryption can help? MMT23 describes a scheme that allows users to request a private key without revealing their identity to the server.

Private sets?

What if instead of nullifers we maintained a set of $\c{user\_id}$'s such that it is only possible to add to the set only once but not possible to query set membership. This seems very challenging as given a $\c{user\_id}$, an attempting to add it will reveal if it was already a member.

Blind signatures?

The user generates a random nullifier. On seeing a valid zksnark the server signs the blinded nullifier. The user unblinds the nullifier and gets a server-signed nullifier.

Not sure how this helps. The server could avoid handing out nullifiers twice, but at this point it's not much different from the server encrypting nullifiers for the users.